package 剑指offer.位运算;

/**
 * 位运算有 5 种
 * 1. &：存在一个 0 结果就是 0
 * 2. |：存在一个 1 结果就是 1
 * 3. ^：相同为 0 不同为 1
 * 4. <<：左移，二进制往左边移动 n 位，最左边的 n 位被挤掉，最右边空出来的补 0
 * 5. >>：右移，二进制往右边移动 n 位，最右边空出来的位置负数补 1 正数补 0
 */
public class 第15题二进制中1的个数 {

    /*
    解法：要想找出二进制中的 1 的个数
    最简单的想法就是：二进制数 & 1
        若包含 1 结果不为 0，计数器加一，然后右移一位继续
        结果为 0 直接右移一位继续
     但是存在无法处理负数的问题，负数全是 1 的话会造成死循环


     最优解，计数一个 1 就删除原二进制数的一个 1
     办法就是让 n-1 然后与他自己 & 运算

     减完 1 后一定与原来的不一致，再和原来的 & 一定会将原来的 1 干掉一个，
     这样一直处理下去直到全部的 1 全被干掉
     */
    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = (n - 1) & n;
        }
        return count;
    }
}

/*
众所周知：(n - 1) & n 的意思就是去掉 n 的二进制里面的一个 1
通过多次循环，就可以把 n 变成 0
 */
